package com.leetcode;

import java.util.ArrayList;

import org.testng.annotations.Test;

public class PalindromePartition {
	public ArrayList<ArrayList<String>> partition(String s) {
		int N = s.length();
		ArrayList<ArrayList<String>>[] res = new ArrayList[N+1];
        for (int i=0; i<=N; i++) {
        	res[i] = new ArrayList();
        }
        res[N].add(new ArrayList<String>());
        
		
        boolean[][] isP = new boolean[N][N];
        for (int len=0; len<N; len++) {
        	for (int i=0; i+len<N; i++) {
        		if (s.charAt(i) == s.charAt(i+len) && 
        			(len<2 || isP[i+1][i+len-1])) {
        			isP[i][i+len] = true;
        		}
        	}
        }
        
        for (int start=N-1; start>=0; start--) {
        	for (int i=start; i<N; i++) {
    			if (isP[start][i]) {
    				String sub = s.substring(start, i+1); 
    				for (ArrayList<String> list : (ArrayList<ArrayList<String>>)res[i+1]) {
    					ArrayList<String> newList = new ArrayList<String>(list);
    					newList.add(0, sub);
    					res[start].add(newList);
    				}
    			}
    		}
        }
        
        return res[0];
    }
	
	@Test
	public void test1() {
		partition("ab");
	}
}
